﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ZeroSumNashSolver
{
    public class MyTimer
    {
        DateTime start;
        public MyTimer()
        {
            start = DateTime.Now;
        }
        public void PrintAndReset(string name)
        {
            TimeSpan sincereset = DateTime.Now - start;
            Console.WriteLine(name + " took " + sincereset.ToString(@"hh\:mm\:ss\.fff"));
            start = DateTime.Now;
        }
        public void Reset()
        {
            start = DateTime.Now;
        }
    }


    public class SimplexResult
    {
        public double[,] inputtable { get; set; }
        public double[,] initial_tableau { get; set; }
        public double[,] complete_tableau { get; set; }
        public List<int> basis { get; set; }
        public double[,] row_player_strategy { get; set; }
        public double[,] column_player_strategy { get; set; }
        public double game_score { get; set; }

        public TimeSpan runtime { get; set; }

        public void Print(string filename = null)
        {
            Action<string> writefunc = null;
            StreamWriter file = null;
            if (filename != null)
            {
                file = File.AppendText("out\\" + filename);
                writefunc = (s) =>
                {
                    file.Write(s);
                };
            }
            else
            {
                writefunc = (s) =>
                {
                    Console.Write(s);
                };
            }

            Matrix.Print(inputtable, "input table", writefunc); writefunc("\n");
            Matrix.Print(initial_tableau, "initial tableau", writefunc); writefunc("\n");
            Matrix.Print(complete_tableau, "completed tableau", writefunc); writefunc("\n");
            Matrix.Print(row_player_strategy, "row player (maximizing)", writefunc); writefunc("\n");
            Matrix.Print(column_player_strategy, "column player (minimizing)", writefunc); writefunc("\n");
            writefunc("value of game: " + game_score.ToString("#0.00")); writefunc("\n\n");
            writefunc("runtime: " + runtime.ToString(@"mm\:ss\.fff")); writefunc("\n\n");

            if (file != null)
            {
                file.Flush();
                file.Close();
            }
        }
    }


    public static class Matrix
    {
        public static double[,] ReadFromFile(string filepath)
        {
            List<string> lines = File.ReadLines(filepath).ToList();
            List<string[]> elements = new List<string[]>();
            List<int> counts = new List<int>();
            foreach (string line in lines)
            {
                string[] temp = line.Split(',').Where(w => !w.Equals("")).ToArray();
                elements.Add(temp);
                counts.Add(temp.GetLength(0));
            }
            double[,] values = new double[lines.Count, counts.Max()];
            for (int i = 0; i < lines.Count; i++)
            {
                for (int j = 0; j < counts.Max(); j++)
                {
                    values[i, j] = double.Parse(elements[i][j]);
                }
            }

            return values;
        }

        public static double[,] Identity(int size)
        {
            if (size <= 0) throw new Exception("Size zero indentity");

            double[,] mat = new double[size, size];

            for (int i = 0; i < size; i++)
                mat[i, i] = 1.0;

            return mat;
        }

        public static double[,] SetAll(double[,] mat, double val)
        {
            for (int i = 0; i < mat.GetLength(0); i++)
                for (int j = 0; j < mat.GetLength(1); j++)
                    mat[i, j] = val;

            return mat;
        }

        public static double[,] Copy(double[,] mat, double increment = 0.0)
        {
            double[,] ret = new double[mat.GetLength(0), mat.GetLength(1)];

            for (int i = 0; i < mat.GetLength(0); i++)
                for (int j = 0; j < mat.GetLength(1); j++)
                    ret[i, j] = mat[i, j] + increment;

            return ret;
        }

        public static double[,] Scale(double[,] mat, double scale)
        {
            double[,] ret = new double[mat.GetLength(0), mat.GetLength(1)];

            for (int i = 0; i < mat.GetLength(0); i++)
                for (int j = 0; j < mat.GetLength(1); j++)
                    ret[i, j] = mat[i, j] * scale;

            return ret;
        }

        public static double[,] Multiply(double[,] left, double[,] right)
        {
            int leftwidth = left.GetLength(0);
            int leftheight = left.GetLength(1);
            int rightwidth = right.GetLength(0);
            int rightheight = right.GetLength(1);

            if (left.GetLength(1) != right.GetLength(0)) throw new Exception("Cannot multiple mismatched dimensions");

            double[,] mat = new double[left.GetLength(0), right.GetLength(1)];

            for (int i = 0; i < left.GetLength(0); i++)
                for (int j = 0; j < right.GetLength(1); j++)
                    for (int z = 0; z < left.GetLength(1); z++)
                    {
                        mat[i, j] += left[i, z] * right[z, j];
                    }

            return mat;
        }

        public static double[,] SubMatrix(double[,] mat, int rowstart, int rowend, int colstart, int colend)
        {
            if (rowstart < 0 || colstart < 0) return null;
            if (rowstart == rowend || colstart == colend) return null;

            double[,] sub = new double[rowend - rowstart, colend - colstart];
            for(int i = 0; i + colstart < colend; i++)
                for(int j = 0; j + rowstart < rowend; j++)
                    sub[j, i] = mat[j + rowstart, i + colstart];

            return sub;
        }

        public static double Determinant(double[,] mat)
        {
            if (mat.GetLength(0) == 1 && mat.GetLength(1) == 1) return mat[0, 0];
            if (mat.GetLength(0) != mat.GetLength(1)) throw new Exception("Determinant of non-square matrix");
            double det = 0.0;

            if (mat.GetLength(0) == 2)
            {
                return mat[0, 0] * mat[1, 1] - mat[1, 0] * mat[0, 1];
            }

            for (int i = 0; i < mat.GetLength(0); i++)
            {
                double val = mat[0, i];
                double[,] lower = ComposeHorizontal(SubMatrix(mat, 1, mat.GetLength(0), 0, i),
                                              SubMatrix(mat, 1, mat.GetLength(0), i + 1, mat.GetLength(1)));


                if (i % 2 == 0)
                    det += val * Determinant(lower);
                else
                    det -= val * Determinant(lower);
            }

            return det;
        }

        public static double[,] Transpose(double[,] mat)
        {
            double[,] transpose = new double[mat.GetLength(0), mat.GetLength(1)];
            for(int i = 0; i < mat.GetLength(0); i++)
                for (int j = 0; j < mat.GetLength(1); j++)
                {
                    transpose[i, j] = mat[j, i];
                }

            return transpose;
        }



        public static double[,] Inverse(double[,] mat)
        {
            if (mat.GetLength(0) != mat.GetLength(1)) throw new Exception("inverse of non-square matrix");

            int h = mat.GetLength(0);

            double[,] a = Matrix.Copy(mat);

            alglib.matinvreport rep;
            int info;

            // 
            // 'Friendly' interface: spdmatrixinverse() accepts and returns symmetric matrix
            // 

            alglib.rmatrixinverse(ref a, out info, out rep);

            if (a == null) return null;
            return a;
        }
        private static void scalerow(double[,] mat, int rowindex, double scale)
        {
            for (int i = 0; i < mat.GetLength(1); i++)
                mat[rowindex, i] *= scale;
        }
        private static void addrow(double[,] mat, int sourcerow, int destrow, double scale = 1.0)
        {
            for (int i = 0; i < mat.GetLength(1); i++)
                mat[destrow, i] += scale * mat[sourcerow, i];
        }
        private static void switchrows(double[,] mat, int a, int b)
        {
            for (int i = 0; i < mat.GetLength(1); i++)
            {
                double temp = mat[a, i];
                mat[a, i] = mat[b, i];
                mat[b, i] = temp;
            }
        }


        public static double[,] GetColumns(double[,] tableau, List<int> columns)
        {
            if (tableau.GetLength(0) != columns.Count) throw new Exception("basis doesnt match matrix size");

            double[,] mat = new double[tableau.GetLength(0), tableau.GetLength(0)];

            for (int i = 0; i < tableau.GetLength(0); i++)
                for (int j = 0; j < tableau.GetLength(0); j++)
                    mat[i, j] = tableau[i, columns[j]];

            return mat;
        }

        public static double[,] RandomValues(int r, int c)
        {
            Random rand = new Random();
            double[,] mat = new double[r, c];
            for (int i = 0; i < r; i++)
                for (int j = 0; j < c; j++)
                    mat[i, j] = rand.NextDouble();
            return mat;
        }

        private static double[,] makeGreaterThanUnity(double[,] mat)
        {            
            double min = double.MaxValue;
            foreach (double m in mat)
                if (m < min) min = m;

            double constant = (min < 1) ? 1.00 - min : 0;
            double[,] temp = Matrix.Copy(mat, constant);
            return temp;
        }
        private static double[,] makeInitialTableau(double[,] mat)
        {
            double[,] tableau = Matrix.ComposeHorizontal(Matrix.SetAll(new double[mat.GetLength(0), 1], 1),
                     Matrix.ComposeHorizontal(mat, Matrix.Scale(Matrix.Identity(mat.GetLength(0)), -1)));

            return tableau;
        }
        private static double[,] makeChangeOfBasis(double[,] oldbasis, double[,] newbasis)
        {
            return Matrix.Multiply(Inverse(newbasis), oldbasis);
        }
        public static SimplexResult Simplex(double[,] initial)
        {
            DateTime begintime = DateTime.Now;

            if (initial.GetLength(0) == 1 || initial.GetLength(1) == 1) return null;

            SimplexResult result = new SimplexResult() { inputtable = initial };


            double[,] gamegreaterthanunity = Matrix.makeGreaterThanUnity(Matrix.Scale(initial, -1.0));

            double[,] tableau = Matrix.makeInitialTableau(gamegreaterthanunity);
            result.initial_tableau = tableau;


            double[,] s_ = null;
            double[,] s_prime = null;


            double[,] oldbasis = null;
            double[,] newbasis = Identity(tableau.GetLength(0));


            //selecting inital basis columns
            List<int> basisindeces = new List<int>() { 1 };
            int minrow = -1;
            double minval = double.MaxValue;
            for (int i = 0; i < tableau.GetLength(0); i++)
                if (tableau[i, 1] < minval)
                {
                    minrow = i;
                    minval = tableau[i, 1];
                }
            for (int i = 0; basisindeces.Count < tableau.GetLength(0); i++)
                if(i != minrow) basisindeces.Add(1 + initial.GetLength(1) + i);
            basisindeces.Sort();



            double[,] alteredtableau = tableau;

            while (true)
            {
                oldbasis = newbasis;
                newbasis = Matrix.GetColumns(tableau, basisindeces);

                double[,] changeofbasis = Matrix.makeChangeOfBasis(oldbasis, newbasis);

                alteredtableau = Matrix.Multiply(changeofbasis, alteredtableau);


                //calculates s_
                s_ = new double[1, alteredtableau.GetLength(1)];
                for (int s = 0; s < alteredtableau.GetLength(1); s++)
                {
                    for (int j = 1; j <= initial.GetLength(1); j++)
                    {
                        if (basisindeces.Contains(j))
                        {
                            for (int i = 0; i < alteredtableau.GetLength(0); i++)
                                s_[0, s] += alteredtableau[i, s] * alteredtableau[i, j];
                        }
                    }
                }

                //calculate s_prime
                s_prime = new double[1, alteredtableau.GetLength(1)];
                for (int s = 0; s < alteredtableau.GetLength(1); s++)
                {
                    if (s >= 1 && s <= initial.GetLength(1))
                        s_prime[0, s] = s_[0, s] - 1;
                    else //if (s >= 1 + init.GetLength(1) && s < newtableau.GetLength(1))
                        s_prime[0, s] = s_[0, s];
                }


                //identify best candidate column
                int indexofmaxs_prime = -1;
                double maxval = 0;
                for (int s = 1; s < alteredtableau.GetLength(1); s++)
                {
                    if (s_prime[0, s] > maxval)
                    {
                        indexofmaxs_prime = s;
                        maxval = s_prime[0, s];
                    }
                }

                //no candidate rows. done
                if (indexofmaxs_prime == -1)
                    break;

                //find point to remove
                double[] ratios = new double[alteredtableau.GetLength(0)];
                for (int i = 0; i < alteredtableau.GetLength(0); i++)
                {
                    ratios[i] = alteredtableau[i, indexofmaxs_prime] / alteredtableau[i, 0];
                }

                int indexofmaxratio = 0;
                for (int i = 0; i < alteredtableau.GetLength(0); i++)
                {
                    if (ratios[i] > ratios[indexofmaxratio]) indexofmaxratio = i;
                }


                //adding and removing same row, done
                if (indexofmaxs_prime == basisindeces[indexofmaxratio])
                    break;


                int indextoadd = indexofmaxs_prime;
                int indextoremove = basisindeces[indexofmaxratio];

                basisindeces.Add(indextoadd);
                basisindeces.Remove(indextoremove);
                basisindeces.Sort();
            }
            alteredtableau = Matrix.ComposeVertical(alteredtableau, s_);
            result.complete_tableau = alteredtableau;
            result.basis = basisindeces;

            double row_player_weight = 0;
            double[,] row_mixed_strat = new double[initial.GetLength(0), 1];
            for (int i = 0; i < initial.GetLength(0); i++)
            {
                row_mixed_strat[i, 0] = s_prime[0, 1 + initial.GetLength(1) + i];
                row_player_weight += s_prime[0, 1 + initial.GetLength(1) + i];
            }
            for (int i = 0; i < initial.GetLength(0); i++)
                row_mixed_strat[i, 0] /= row_player_weight;

            double column_player_weight = 0;
            double[,] column_mixed_strat = new double[1, initial.GetLength(1)];
            for (int i = 0; i < initial.GetLength(0); i++)
            {
                if (basisindeces[i] <= initial.GetLength(1))
                {
                    column_mixed_strat[0, basisindeces[i] - 1] = alteredtableau[i, 0];
                    column_player_weight += alteredtableau[i, 0];
                }
            }
            for (int i = 0; i < initial.GetLength(1); i++)
                column_mixed_strat[0, i] /= column_player_weight;


            result.row_player_strategy = row_mixed_strat;
            result.column_player_strategy = column_mixed_strat;

            for (int i = 0; i < initial.GetLength(0); i++)
                for (int j = 0; j < initial.GetLength(1); j++)
                    result.game_score += row_mixed_strat[i, 0] * column_mixed_strat[0, j] * initial[i, j];


            DateTime finishtime = DateTime.Now;
            result.runtime = finishtime - begintime;

            return result;
        }

        public static double[,] GetColumn(double[,] mat, int column)
        {
            return SubMatrix(mat, 0, mat.GetLength(0), column, column + 1);
        }
        public static double[,] GetRow(double[,] mat, int row)
        {
            return SubMatrix(mat, row, row + 1, 0, mat.GetLength(1));
        }
        public static double[,] ComposeVertical(double[,] top, double[,] bottom)
        {
            if(top == null && bottom == null) return null;
            if (top == null) return bottom;
            if (bottom == null) return top;

            if (top.GetLength(1) != bottom.GetLength(1)) throw new Exception("Cannot compose mismatched matrices");

            double[,] mat = new double[top.GetLength(0) + bottom.GetLength(0), top.GetLength(1)];

            for (int i = 0; i < top.GetLength(1); i++)
            {
                for (int j = 0; j < top.GetLength(0); j++)
                    mat[j, i] = top[j, i];

                for (int j = 0; j < bottom.GetLength(0); j++)
                    mat[j + top.GetLength(0), i] = bottom[j, i];
            }

            return mat;
        }
        public static double[,] ComposeHorizontal(double[,] left, double[,] right)
        {
            if (left == null && right == null) return null;
            if (left == null) return right;
            if (right == null) return left;

            if (left.GetLength(0) != right.GetLength(0)) throw new Exception("Cannot compose mismatched matrices");

            double[,] mat = new double[left.GetLength(0), left.GetLength(1) + right.GetLength(1)];

            for (int i = 0; i < left.GetLength(0); i++)
            {
                for (int j = 0; j < left.GetLength(1); j++)
                    mat[i, j] = left[i, j];

                for (int j = 0; j < right.GetLength(1); j++)
                    mat[i, j + left.GetLength(1)] = right[i, j];
            }

            return mat;
        }

        public static void Print(double[,] mat, string name = null, Action<string> writefunc = null)
        {
            if (writefunc == null) return;

            if (mat == null)
            {
                writefunc("[null]\n");
                return;
            }

            int[] columnwidths = new int[mat.GetLength(1)];
            for (int c = 0; c < mat.GetLength(1); c++)
            {
                for (int e = 0; e < mat.GetLength(0); e++)
                {
                    string formatted = mat[e, c].ToString("#0.000");
                    int strlen = formatted.Length;
                    if (strlen > columnwidths[c]) columnwidths[c] = strlen;
                }
            }


            if (name != null) writefunc(name + ": ");
            writefunc("[");
            for (int i = 0; i < mat.GetLength(0); i++)
            {
                if (i > 0)
                {
                    if (name != null) for (int s = 0; s < name.Length + 2; s++) writefunc(" ");
                    writefunc("  ");
                }
                else
                {
                    writefunc("[");
                }

                for (int j = 0; j < mat.GetLength(1); j++)
                {
                    writefunc(" ");
                    string formatted = mat[i, j].ToString("#0.000");
                    for (int p = 0; p < columnwidths[j] - formatted.Length; p++)
                        writefunc(" ");

                    writefunc(formatted);
                }


                writefunc(" ]");
                if (i + 1 != mat.GetLength(0))
                    writefunc("\n");

            }
            writefunc("]\n");
        }
    }
}
